1458D - Flip and Reverse - CodeForces Solution

#include <bits/stdc++.h>
using namespace std;
#define debug(fmt, ...) \
  fprintf(stderr, "[%d] : " fmt "\n", __LINE__, ##__VA_ARGS__)
bool Mbe;
using ll = long long;
constexpr int N = 1e6 + 10;
int n, top, prf[N], stk[N], cnt[N][2];
string str;
void dfs(int u) {
  while (cnt[u][0]) --cnt[u][0], --cnt[u - 1][1], dfs(u - 1);
  while (cnt[u][1]) --cnt[u][1], --cnt[u + 1][0], dfs(u + 1);
  stk[top++] = u;
}
void mian() {
  cin >> str;
  n = str.size();
  str = " " + str, prf[0] = n;
  for (int i = 1; i <= n; ++i)
    prf[i] = prf[i - 1] + (str[i] == '1' ? 1 : -1);
  for (int i = 0; i <= n + n; ++i) cnt[i][0] = cnt[i][1] = 0;
  for (int i = 1; i <= n; ++i)
    if (prf[i - 1] < prf[i]) {
      ++cnt[prf[i]][0], ++cnt[prf[i - 1]][1];
    } else {
      ++cnt[prf[i]][1], ++cnt[prf[i - 1]][0];
    }
  top = 0, dfs(n);
  assert(top == n + 1);
  reverse(stk, stk + top);
  string ans(n, '0');
  for (int i = 1; i <= n; ++i)
    ans[i - 1] = stk[i] > stk[i - 1] ? '1' : '0';
  cout << ans << '\n';
}
bool Med;
int main() {
  // debug("Mem: %.4lfMB.", fabs(&Med - &Mbe) / 1048576);
  cin.tie(0)->sync_with_stdio(0);
  int cas;
  cin >> cas;
  while (cas--) mian();
  return 0;
}//537963017544265770